package com.fenqing.leetcode.code.t0_200.t0_100;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

/**
 * @author fenqing
 */
public class Topic069 extends Topic {
    /**
     * 构造器
     *
     * @param input 输入
     */
    public Topic069(String input) {
        super(input);
    }

    /**
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * 示例 1：
     * 输出：2
     * 示例 2：
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     * @param x x
     * @return 结果
     */
    @Execute
    public int mySqrt(int x) {
        if(x == 0){
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        long p = 2, q = x >> 1;
        while (p < q) {
            long mid = (p + q) / 2;
            // 计算出平方
            long num = mid * mid;

            if (num > x) {
                // 如果结果大于目标值
                q = mid;
            } else if (num < x) {
                // 如果结果小于目标值
                p = mid + 1;
            } else {
                return (int) mid;
            }
        }
        return (int) (p * p <= x ? p : p - 1);
    }

    public static void main(String[] args) {
        Topic069 topic069 = new Topic069("5");
        Integer run = topic069.run();
        System.out.println(run);
    }

}
